#include "main/utils.h"
using namespace std;

int pathSumCore(int row, int col, const vector<vector<int>>& cost, vector<vector<int>>& dp) {
  if (dp[row][col] == 0) {
    if (row == 0 && col == 0) {
      dp[row][col] = cost[0][0];
    } else if (row == 0) {
      dp[row][col] = pathSumCore(row, col - 1, cost, dp) + cost[row][col];
    } else if (col == 0) {
      dp[row][col] = pathSumCore(row - 1, col, cost, dp) + cost[row][col];
    } else {
      dp[row][col] = min(pathSumCore(row - 1, col, cost, dp), pathSumCore(row, col - 1, cost, dp)) + cost[row][col];
    }
  }
  return dp[row][col];
}

int pathSum1(const vector<vector<int>>& cost) {
  int rows = cost.size();
  int cols = cost[0].size();

  vector<vector<int>> dp;
  dp.resize(rows);
  for (int i = 0; i < rows; ++i) {
    dp[i].resize(cols, 0);
  }
  return pathSumCore(rows - 1, cols - 1, cost, dp);
}

int pathSum2(const vector<vector<int>>& cost) {
  int rows = cost.size();
  int cols = cost[0].size();

  vector<vector<int>> dp;
  dp.resize(rows);
  for (int i = 0; i < rows; ++i) {
    dp[i].resize(cols, 0);
  }
  dp[0][0] = cost[0][0];
  for (int j = 1; j < cols; ++j) {
    dp[0][j] = dp[0][j - 1] + cost[0][j];
  }
  for (int i = 1; i < rows; ++i) {
    dp[i][0] = dp[i - 1][0] + cost[i][0];
    for (int j = 1; j < cols; ++j) {
      dp[i][j] = min(dp[i - 1][j],  dp[i][j - 1]) + cost[i][j];
    }
  }
  return dp[rows - 1][cols - 1];
}

int pathSum3(const vector<vector<int>>& cost) {
  int rows = cost.size();
  int cols = cost[0].size();

  vector<int> dp(cols, 0);
  dp[0] = cost[0][0];
  for (int i = 1; i < cols; ++i) {
    dp[i] = dp[i - 1] + cost[0][i];
  }
  for (int i = 1; i < rows; ++i) {
    dp[0] = dp[0] + cost[i][0];
    for (int j = 1; j < cols; ++j) {
      dp[j] = min(dp[j], dp[j - 1]) + cost[i][j];
    }
  }
  return dp[cols - 1];
}

int main() {
  vector<vector<int>> cost = {{1, 3, 1}, {2, 5, 2}, {3, 4, 1}};
  cout << pathSum1(cost) << endl;
  cout << pathSum2(cost) << endl;
  cout << pathSum3(cost) << endl;

  return 0;
}
